//(0, 0)->(n-1, n-1) 可走最短路径中的最大值 二分
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    const int INF=0x3f3f3f3f;
    const int nxt[4][2]={{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    int n;
    bool checkpos(int x, int y) {return 0<=x&&x<n&&0<=y&&y<n;}

    bool check(vector<vector<int>> &grid, vector<vector<int>> &vis, int x, int y, int mx)
    {
        if(x==n-1&&y==n-1) return true; //到达终点
        vis[x][y]=mx;
        printf("check(%d, %d, %d)\n", mx, x, y);
        for(auto &[dx, dy]:nxt)
        {
            int nx=x+dx, ny=y+dy;
            //  位置在范围内    &&  权值在范围内   &&当前路径没有在当前限制下访问过&&可以更新
            if(checkpos(nx, ny)&&grid[nx][ny]<=mx&&vis[nx][ny]!=mx&&check(grid, vis, nx, ny, mx)) 
                return true;
        }
        return false;
    }

    int swimInWater(vector<vector<int>>& grid) {
        n=grid.size();
        vector<vector<int>> vis(n, vector<int>(n, -1));
        int left=max(grid[0][0], grid[n-1][n-1])-1, right=n*n-1;
        while(left+1<right){
            int mid=left+(right-left)/2;
            (check(grid, vis, 0, 0, mid)?right:left)=mid;
        }
        return right;
    }
};

int main()
{
    vector<vector<int>> grid={{0,1,2,3,4},
                              {24,23,22,21,5},
                              {12,13,14,15,16},
                              {11,17,18,19,20},
                              {10,9,8,7,6}};
    Solution solution;
    cout <<solution.swimInWater(grid) << endl;
                             
    return 0;
}